package tulingxueyuan117;

import java.util.HashMap;

/**
 * Author: Zhang Dongwei
 * Date: 2022/10/27 12:40
 * 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
 *
 * 例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class p19_立案表中倒数第k个节点_剑指offer22 {
    public static void main(String[] args) {
        ListNode listNode = new  ListNode(1);
        ListNode listNode1 = new ListNode(2);
        ListNode listNode2 = new ListNode(3);
        ListNode listNode3 = new ListNode(4);
        ListNode listNode4 = new ListNode(5);
        ListNode listNode5 = new ListNode(6);
        listNode.next = listNode1;
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;

        ListNode res = getKthFromEnd(listNode, 3);
        System.out.println(res.val);

    }

//    遍历一次得到长度，再遍历到l-k的位置返回结果
    /*
    执行用时：
0 ms
, 在所有 Java 提交中击败了
100.00%
的用户
内存消耗：
39.3 MB
, 在所有 Java 提交中击败了
67.83%
的用户
    * */
//    public static ListNode getKthFromEnd(ListNode head, int k) {
//        ListNode p = head;
//        int l = 0;
//        while (p!=null){
//            l++;
//            p = p.next;
//        }
//        int n = l - k;
//        int w = 0;
//        while (w<n){
//            head = head.next;
//            w++;
//        }
//        return head;
//    }

    // (视频解法)快慢指针，快指针先移动k-1个，然后同时移动到快指针到尾部即可
    /*
    执行用时：
0 ms
, 在所有 Java 提交中击败了
100.00%
的用户
内存消耗：
39.2 MB
, 在所有 Java 提交中击败了
85.81%
的用户
    * */
    public static ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;
        for(int i=0; i<=k-1; i++) fast =fast.next;
        while (fast!=null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}
